算法复习 (三) 图-无向图（未完成）

算法复习 (三) 图-无向图

一. 图

1.1 应用场景

• 地图。正在计划旅行的人也许想知道“从普罗维登斯到普林斯顿的最短路线”。对最短路径上经历过交通堵塞的旅行者可能会问：“从普罗维登斯到普林斯顿的哪条路线最快？”要回答这些问题，我们都要处理有关结点（十字路口）之间多条连接（公路）的信息。
• 网页信息。当我们在浏览网页时，页面上都会包含其他网页的引用（链接）。通过单击链接，我们可以从一个页面跳到另一个页面。整个互联网就是一张图，结点是网页，连接就是超链接。图算法是帮助我们在网络上定位信息的搜索引擎的关键组件。
• 电路。在一块电路板上，晶体管、电阻、电容等各种元件是精密连接在一起的。我们使用计算机来控制制造电路板的机器并检查电路板的功能是否正常。我们既要检查短路这类简单问题，也要检查这幅电路图中的导线在蚀刻到芯片上时是否会出现交叉等复杂问题。第一类问题的答案仅取决于连接（导线）的属性，而第二个问题则会涉及导线、各种元件
  以及芯片的物理特性等详细信息。
• 任务调度。商品的生产过程包含了许多工序以及一些限制条件，这些条件会决定某些任务的先后次序。如何安排才能在满足限制条件的情况下用最少的时间完成这些生产工序呢？
  商业交易。零售商和金融机构都会跟踪市场中的买卖信息。在这种情形下，一条连接可以表示现金和商品在买方和卖方之间的转移。在此情况下，理解图的连接结构原理可能有助于增强人们对市场的理解。
• 配对。学生可以申请加入各种机构，例如社交俱乐部、大学或是医学院等。这里结点就对应学生和机构，而连接则对应递交的申请。我们希望找到申请者与他们感兴趣的空位之间配对的方法。
• 计算机网络。计算机网络是由能够发送、转发和接收各种消息的站点互相连接组成的。我们感兴趣的是这种互联结构的性质，因为我们希望网络中的线路和交换设备能够高效率地处理网络流量。
• 软件。编译器会使用图来表示大型软件系统中各个模块之间的关系。图中的结点即构成整个系统的各种类和模块，连接则为类的方法之间的可能调用关系（静态分析），或是系统运行时的实际调用关系（动态分析）。我们需要分析这幅图来决定如何以最优的方式为程序分配资源。
• 社交网络。当你在使用社交网站时，会和你的朋友之间建立起明确的关系。这里，结点对应人而连接则联系着你和你的朋友或是关注者。分析这些社交网络的性质是当前图算法的一个重要应用。对它感兴趣的不止是社交网络的公司，还包括政治、外交、娱乐、教育、市场等许多其他机构。

应用	结点	连接
地图	十字路口	公路
网络内容	网页	超链接
电路	元器件	导线
任务调度	任务	限制条件
商业交易	客户	交易
配对	学生	申请
计算机网络	网站	物理连接
软件	方法	调用关系
社交网络	人	友谊关系

1.2 常用术语

• 某个顶点的度数即为依附于它的边的总数。
• 子图是由一幅图的所有边的一个子集（以及它们所依附的所有顶点）组成的图。许多计算问题都需要识别各种类型的子图，特别是由能够顺序连接一系列顶点的边所组成的子图。
• 路径是由边顺序连接的一系列顶点。
• 简单路径是一条没有重复顶点的路径。环是一条至少含有一条边且起点和终点相同的路径。
• 简单环是一条（除了起点和终点必须相同之外）不含有重复顶点和边的环。
• 路径或者环的长度为其中所包含的边数。
• 当两个顶点之间存在一条连接双方的路径时，我们称一个顶点和另一个顶点是连通的。
• 如果从任意一个顶点都存在一条路径到达另一个任意顶点，我们称这幅图是连通图。一幅非连通的图由若干连通的部分组成，它们都是其极大连通子图。
• 无环图是一种不包含环的图。
• 图的密度是指已经连接的顶点对占所有可能被连接的顶点对的比例。在稀疏图中，被连接的顶点对很少；而在稠密图中，只有少部分顶点对之间没有边连接。
• 二分图是一种能够将所有结点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的部分。

1.3 图与树的关系

树是一幅无环连通图。互不相连的树组成的集合称为森林。连通图的生成树是它的一幅子图，它含有图中的所有顶点且是一棵树。图的生成树森林是它的所有连通子图的生成树的集合。

当且仅当一幅含有V个结点的图满足下列 5 个条件之一时，它就是一棵树：

• G有V-1条边且不含有环；
• G有V-1条边且是连通的；
• G是连通的，但删除任意一条边都会使它不再连通；
• G是无环图，但添加任意一条边都会产生一条环；
• G中的任意一对顶点之间仅存在一条简单路径。

1.4 四种图模型

4 种最重要的图模型：

• 无向图（简单连接）
• 有向图（连接有方向性）
• 加权图（连接带有权值）
• 加权有向图（连接既有方向性又带有权值）

二. 无向图

（1）概念

定义：图是由一组顶点和一组能够将两个顶点相连的边组成的。

一般使用 0 至 V-1 来表示一张含有 V 个顶点的图中的各个顶
点。用 v-w 的记法来表示连接 v 和 w 的边，w-v 是这条边的另一种表示方法。

绘制出的图有时会误导我们，因为图的定义和绘出的图像是无关的。

特殊的图。我们的定义允许出现两种简单而特殊的情况：

• 自环，即一条连接一个顶点和其自身的边；
• 连接同一对顶点的两条边称为平行边。

数学家常常将含有平行边的图称为多重图，而将没有平行边或自环的图称为简单图。后续不会出现这种特殊情况，所以用两个顶点就可以指代一条边了。

public class Bag<Item> implements Iterable<Item> {
    private Node first; // 链表的首结点

    private class Node {
        Item item;
        Node next;
    }

    public void add(Item item) { // 和Stack 的push() 方法完全相同
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
    }

    public Iterator<Item> iterator() {
        return new ListIterator();
    }

    private class ListIterator implements Iterator<Item> {
        private Node current = first;

        public boolean hasNext() {
            return current != null;
        }

        public void remove() {
        }

        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

public class Graph {
    private final int V; // 顶点数目
    private int E; // 边的数目
    private Bag<Integer>[] adj; // 邻接表：数组+链表

    public Graph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[]) new Bag[V]; // 创建邻接表
        for (int v = 0; v < V; v++) // 将所有链表初始化为空
            adj[v] = new Bag<Integer>();
    }

    public Graph(In in) {
        this(in.readInt()); // 读取V并将图初始化
        int E = in.readInt(); // 读取E
        for (int i = 0; i < E; i++) { // 添加一条边
            int v = in.readInt(); // 读取一个顶点
            int w = in.readInt(); // 读取另一个顶点
            addEdge(v, w); // 添加一条连接它们的边
        }
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public void addEdge(int v, int w) {
        adj[v].add(w); // 将w添加到v的链表中
        adj[w].add(v); // 将v添加到w的链表中
        E++;
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
}

三. 深度优先搜索

深度优先搜索算法DFS

四. 广度优先搜索

广度优先搜索算法BFS

---

参考：

🔗 《算法-第4版》